//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"

namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {
  for (size_t i = 0; i < num_frames; i++) {
    index_.emplace_back(FrameEntry());
  }
}

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  // first pop in history_queue
  bool ret = false;
  std::scoped_lock<std::mutex> lock(latch_);
  if (!history_queue_.empty()) {
    auto iter = history_queue_.rbegin();
    while (iter != history_queue_.rend()) {
      if (index_[*iter].evictable_) {
        *frame_id = *iter;
        history_queue_.remove(*iter);
        ret = true;
        break;
      }
      iter++;
    }
  }
  if (!ret && !lru_queue_.empty()) {
    auto iter = lru_queue_.rbegin();
    while (iter != lru_queue_.rend()) {
      if (index_[*iter].evictable_) {
        *frame_id = *iter;
        lru_queue_.remove(*iter);
        ret = true;
        break;
      }
      iter++;
    }
  }
  if (ret) {
    --curr_size_;
    index_[*frame_id].evictable_ = true;
    index_[*frame_id].ref_ = 0;
  }
  return ret;
}

void LRUKReplacer::RecordAccess(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  size_t k = ++index_[frame_id].ref_;
  // add  new frame_id
  if (k == 1) {
    ++curr_size_;
    index_[frame_id].pos_ = history_queue_.insert(history_queue_.begin(), frame_id);
    return;
  }
  // if the ref of frame is equal to k_,remove from history_queue,insert into the head of lru_queue
  if (k == k_) {
    history_queue_.remove(frame_id);
    index_[frame_id].pos_ = lru_queue_.insert(lru_queue_.begin(), frame_id);
  } else if (k > k_) {
    lru_queue_.remove(frame_id);
    index_[frame_id].pos_ = lru_queue_.insert(lru_queue_.begin(), frame_id);
  }
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  std::scoped_lock<std::mutex> lock(latch_);
  if (index_[frame_id].evictable_) {
    if (!set_evictable) {
      --curr_size_;
    }
  } else {
    if (set_evictable) {
      ++curr_size_;
    }
  }
  index_[frame_id].evictable_ = set_evictable;
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  if (frame_id < 0 || frame_id >= static_cast<int>(replacer_size_)) {
    return;
  }
  // this frame is not evictable
  if (!index_[frame_id].evictable_) {
    throw("this frame is not evictable`.");
  }
  if (index_[frame_id].ref_ == 0) {
    return;
  }
  if (index_[frame_id].ref_ < k_) {
    history_queue_.erase(index_[frame_id].pos_);
  } else {
    lru_queue_.erase(index_[frame_id].pos_);
  }
  index_[frame_id] = FrameEntry();
  --curr_size_;
}

auto LRUKReplacer::Size() -> size_t { return curr_size_; }

}  // namespace bustub
